package leetcode.search;

import java.util.LinkedList;

/**
 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填

 从边界出发吧，先把边界上和 O 连通点找到, 把这些变成 B,然后遍历整个 board 把 O 变成 X, 把 B 变成 O

 */
public class Solve130 {
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public void solve(char[][] board) {

        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) return;
        int row = board.length;
        int col = board[0].length;

//        先把边界上和 O 连通点找到, 把这些变成 B
        for (int j = 0; j < col; j++) {
            // 第一行
            if (board[0][j] == 'O') dfs(0, j, board);
            // 最后一行
            if (board[row - 1][j] == 'O') dfs(row - 1, j, board);
        }

        for (int i = 0; i < row; i++) {
            // 第一列
            if (board[i][0] == 'O') dfs(i, 0, board);
            // 最后一列
            if (board[i][col - 1] == 'O') dfs(i, col - 1, board);
        }

        //  然后遍历整个 board 把 O 变成 X, 把 B 变成 O
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X'; //吧0变回X
                if (board[i][j] == 'B') board[i][j] = 'O'; //把B变回0
            }
        }
    }
    ////        DFS 把边界上和 O 连通点找到, 把这些变成 B
    void dfs(int i,int j,char[][]board){
            board[i][j] ='B';

        for (int[] dir : dirs) {
            int x = i+dir[0];
            int y = j+dir[1];

            if(x>=0 && x< board.length &&
               y>=0 && y< board[0].length &&
              board[x][y] =='O' ){

                dfs(x,y,board);
            }
        }
    }


    void bfs(int i,int j,char[][]board){
        int row = board.length;
        int col = board[0].length;

        LinkedList<int []> que = new LinkedList<>();
        que.push(new int[]{i,j});

        while (!que.isEmpty()){

            int[] points = que.poll();
            int x = points[0];
            int y = points[1];

            if(x>=0 && x< board.length &&
                    y>=0 && y< board[0].length &&
                    board[x][y] =='O' ){
                board[x][y] = 'B';

                for (int[] dir : dirs) {
                    int temX = i + dir[0];
                    int temY = j + dir[1];
                    que.push(new int[]{temX,temY});
                }
            }
        }
    }
}